package lib

import "strings"

func init() {
	Probs = append(Probs, Problem{
		Num:         331,
		Discription: "验证二叉树的前序序列化（孩子为nil也会记录，要不然没法做）",
		Level:       2,
		Labels: map[string]int{
			"栈":    1,
			"计数栈":    1,
			"拓扑排序": 1,
			"二叉树":  1,
		},
	})
}

//思路：在遍历中，除开始和结束时的任意时刻，构造中的树的度不能==0（要不然就表示遍历结束了）
func IsValidSerialization(preorder string) bool {
	nodes := strings.Split(preorder, ",")
	n := len(nodes)
	//如果第一个节点就是nil，那么只有在整个序列只有nil的情况下才为true，否则为false
	if nodes[0] == "#" {
		return n == 1
	}

	//从根节点开始，度为2
	count := 2
	for i := 1; i < n; i++ {
		node := nodes[i]
		if node == "#" {
			//空节点占用一个度
			count--
			//如果某一时刻度没了，且没遍历完，false
			if count == 0 && i < n-1 {
				return false
			}
		} else {
			//非空节点先占用一个度，再贡献两个度
			count++
		}
	}

	//最后看有无多余的度
	return count == 0
}
